class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        int n = position.size();
        sort(position.begin(), position.end());
        long long left = 1;
        long long right = position[n - 1] - position[0];
        long long mid = 0;
        if (m == 2) {
            return position[n - 1] - position[0];
        }
        else {
            int count = 1;
            int ans = 0;
            while (left <= right) {
                long long temp = position[0];
                mid = (right + left) / 2;
                for (int i = 0; i < n; i++) {
                    if (position[i] - temp >= mid) {
                        count++;
                        temp = position[i];
                    }
                }
                if (count >= m) {
                    left = mid + 1;
                    ans = mid;
                }
                else {
                    right = mid - 1;
                }
                count = 1;
            }
            return ans;
        }
    }
};